package ch5.part3;

import java.util.EmptyStackException;
import java.util.Stack;

/**
 * 实现一个栈结构，使得其pop()、push()、getMin()的时间复杂度均为O(1)
 * 本例空间复杂度：O(n) = n
 * @author liuwanxiang
 * @version 2019/06/17
 */
public class MinStack {

    private Stack<Integer> mainStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    private void push(Integer data) {
        mainStack.push(data);
        if (minStack.empty() || minStack.peek() >= data) {
            minStack.push(data);
        }
    }

    private Integer pop() {
        if (mainStack.empty()) {
            throw new EmptyStackException();
        }
        if (mainStack.peek().equals(minStack.peek())) {
            minStack.pop();
        }
        return mainStack.pop();
    }

    private Integer getMin(){
        if (mainStack.empty()) {
            throw new EmptyStackException();
        }
        return minStack.peek();
    }

    public static void main(String[] args) {

        MinStack stack = new MinStack();
        stack.push(9);
        stack.push(4);
        stack.push(7);
        stack.push(3);
        stack.push(8);
        stack.push(5);

        System.out.println(stack.getMin());

        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());

        System.out.println(stack.getMin());

        System.out.println(stack.pop());
        System.out.println(stack.pop());

        System.out.println(stack.getMin());

        System.out.println(stack.pop());
    }

}
